#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


class Solution {
    public:
        int minPathSum(vector<vector<int> > &grid) {
            int m = grid.size();
            int n = grid[0].size();
            vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == 1) dp[i][j] = dp[i][j-1] + grid[i-1][j-1];
                    else if (j == 1) dp[i][j] = dp[i-1][j] + grid[i-1][j-1];
                    else dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]; 
                }
            }
            return dp[m][n];
        }
};

//add better code which do not need 
    int minPathSum(vector<vector<int> > &grid) {
        for (int i = 1; i < grid.size(); i++) {
            grid[i][0] += grid[i-1][0];
        }   

        for (int j = 1; j < grid[0].size(); j++) {
            grid[0][j] += grid[0][j-1];
        }   

        for (int i = 1; i < grid.size(); i++) {
            for (int j = 1; j < grid[0].size(); j++) {
                grid[i][j] = grid[i][j] + min(grid[i-1][j] , grid[i][j-1]);
            }   
        }   
        return grid[grid.size()-1][grid[0].size()-1];
    }   

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
